package algorithm.recursionAndbacktrack.combination.p216;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> combinations = new ArrayList<>();
        combinationSum3(k, n, 1, combinations, new ArrayDeque<>());

        return combinations;
    }

    private void combinationSum3(int k, int n, int startNum, List<List<Integer>> combinations, ArrayDeque<Integer> combination) {
        if (n <= 0 && combination.size() == k) {
            if(n == 0)
                combinations.add(new ArrayList<>(combination));
            return;
        }

        for (int i = startNum; i <= 9; i++) {
            combination.addLast(i);
            combinationSum3(k, n - i, i + 1, combinations, combination);
            combination.removeLast();
        }
    }

    public static void main(String[] args) {
        System.out.println(new Solution().combinationSum3(3, 9));
    }
}